1. Field of the Invention
This invention relates generally to transactional memory computer systems and, more specifically, to a system and method for implementing transactional locking using reader-lists.
2. Description of the Related Art
Shared-memory computer systems allow multiple threads of execution to access and operate on the same memory locations. In such systems, it is often important that a thread execute a series of instructions as a single atomic block. Such an atomic block may be known as a critical section. Any other thread that observes memory values resulting from a partial execution of a critical section may behave incorrectly.
Critical sections are traditionally protected by locks. That is, before a thread may execute a critical section, it must first acquire and hold one or more locks associated with the critical section. While it holds the lock, no other thread may execute a critical section protected by that lock. This mechanism may be known as mutual exclusion. The pitfalls of mutual exclusion mechanisms are numerous and well known. They include dead-lock, race conditions, priority inversions, software complexity, and performance limitations.
Transactional memory is a mechanism that allows a thread to execute a critical section as a speculative transaction, that is, either completely and atomically or not at all. The instructions comprising a transaction may be executed and then either “committed”, allowing the aggregate effect to be seen by all other threads, or “aborted”, allowing no effect to be seen. Transactional attempts that commit may be said to have “succeeded”, while those that abort may be said to have “failed”. If a transaction aborts, the thread may retry executing the transaction. Transactional memory may be implemented in hardware, software, or a combination thereof.
Transactional Locking (TL) is a software-based, transactional memory technique that may allow multiple threads to execute critical sections concurrently, as transactions. If a data conflict occurs, one or more of the transactions involved may abort execution of the critical section. For example, a data conflict may occur when one thread attempts to commit a transaction that read a value from memory if that value has been modified by another thread since being read.